//class Solution {
//public:
//    bool checkSubTree(TreeNode* t1, TreeNode* t2) {
//        if (t2 == nullptr) return true;
//        if (t1 == nullptr) return false;
//        if (t1->val == t2->val && CheckTree(t1, t2)) return true;
//        return checkSubTree(t1->left, t2) || checkSubTree(t1->right, t2);
//    }
//
//    bool CheckTree(TreeNode* t1, TreeNode* t2)
//    {
//        if (t1 == nullptr && t2 == nullptr) return true;
//        if (t1 == nullptr || t2 == nullptr) return false;
//        if (t1->val != t2->val) return false;
//        return CheckTree(t1->left, t2->left) && CheckTree(t1->right, t2->right);
//    }
//};



class Solution {
public:
    unordered_map<long long, int> prefix;

    int dfs(TreeNode* root, long long curr, int sum) {
        if (!root) 
        {
            return 0;
        }

        int ret = 0;
        curr += root->val;
        if (prefix.count(curr - sum)) 
        {
            ret = prefix[curr - sum];
        }

        prefix[curr]++;
        ret += dfs(root->left, curr, sum);
        ret += dfs(root->right, curr, sum);
        prefix[curr]--;

        return ret;
    }

    int pathSum(TreeNode* root, int sum) 
    {
        prefix[0] = 1;
        return dfs(root, 0, sum);
    }
};